import time


class Solution:
    mid_dic = {0: 1, 1: 1}

    def numTrees(self, n: int) -> int:
        Solution.mid_dic[n] = self.search(n)
        return Solution.mid_dic[n]

    def search(self, n: int):
        if n in self.mid_dic:
            return self.mid_dic[n]
        res = 0
        for i in range(1, n+1):
            res += self.search(i-1) * self.search(n-i)
        return res


a = Solution()
for i in range(20):
    start = time.time()
    print(i, a.numTrees(i), time.time()-start)
